package com.atguigui.leetcode;

/**
 * * P面试题 17.09.第 k 个数
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2022/9/28 22:44
 */
public class GetKthMagicNumberLcci {
    public static void main(String[] args) {
        Solution solution = new GetKthMagicNumberLcci().new Solution();
        // TO TEST
    }

    class Solution {
        public int getKthMagicNumber(int k) {
            int[] dp = new int[k + 1];
            dp[1] = 1;
            int p3 = 1, p5 = 1, p7 = 1;
            //遍历循环从2开始
            for (int i = 2; i <= k; i++) {
                //素因素为3、5、7的所有数的可能
                int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
                //找到三个中最小的质数
                dp[i] = Math.min(Math.min(num3, num5), num7);
                if (dp[i] == num3) {
                    p3++;
                }
                if (dp[i] == num5) {
                    p5++;
                }
                if (dp[i] == num7) {
                    p7++;
                }
            }
            return dp[k];
        }
    }
}
